package com.aqie.easy.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 888 公平的糖果交换
 */
public class FairCandySwap {
    /**
     * 1, 170ms
     * @param A
     * @param B
     * @return
     */
    public int[] fairCandySwap(int[] A, int[] B) {
        int[] ans = new int[2];
        int totalA = sum(A);
        int totalB = sum(B);
        int difference = (totalA - totalB) / 2;
        System.out.println("d: " + difference);
        for (int aA : A) {
            int targetB = aA - difference;
            System.out.println(aA + " - " + targetB);
            System.out.println(indexOf(B, targetB));
            if (!contains(B, targetB)) {
                continue;
            }
            ans[0] = aA;
            ans[1] = targetB;
            System.out.println(aA + " " + targetB);
            return ans;
        }
        return ans;
    }

    private boolean contains(int[] a, int key){
        for (int anA : a) {
            if (anA == key) return true;
        }
        return false;
    }


    /**
     * 二分查找数组必须有序 ！！！
     * @param a
     * @param key
     * @return
     */
    public int indexOf(int[] a, int key) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }
    private int sum(int[] arr){
        int N = arr.length;
        int total = 0;
        for (int anArr : arr) {
            total += anArr;
        }
        return total;
    }


    /**
     * 2. 使用set 34ms
     * @param A
     * @param B
     * @return
     */
    public int[] fairCandySwap2(int[] A, int[] B) {
        int sa = 0, sb = 0;  // sum of A, B respectively
        for (int x: A) sa += x;
        for (int x: B) sb += x;
        int delta = (sb - sa) / 2;
        // If Alice gives x, she expects to receive x + delta

        Set<Integer> setB = new HashSet<>();
        for (int x: B) setB.add(x);

        for (int x: A)
            if (setB.contains(x + delta))
                return new int[]{x, x + delta};

        throw null;
    }



    public static void main(String[] args) {
        FairCandySwap fcs = new FairCandySwap();
        int[] A = {35,17,4,24,10};
        int[] B = {63,21};
        /*int[] A = {1,1};
        int[] B = {2,2};*/
        System.out.println(Arrays.toString(fcs.fairCandySwap(A, B)));
    }
}
